/*
 * @lc app=leetcode.cn id=12 lang=cpp
 *
 * [12] 整数转罗马数字
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_map>

using namespace std;
// @lc code=start
class Solution {
private:
    vector<int> nums = {1,4,5,9,10,40,50,90,100,400,500,900,1000};
    unordered_map<int, string> symbolValues = {
        {1,"I"},
        {4,"IV"},
        {5,"V"},
        {9,"IX"},
        {10,"X"},
        {40,"XL"},
        {50,"L"},
        {90,"XC"},
        {100,"C"},
        {400,"CD"},
        {500,"D"},
        {900,"CM"},
        {1000,"M"}
    };
public:
    string intToRoman(int num) {
        string ret;
        int i = nums.size()-1;
        while(num) {
            if(num >= nums[i]) {
                num -= nums[i];
                ret += symbolValues[nums[i]];
            }else {
                i--;
            }
        }
        return ret;
    }
};
// @lc code=end

